These problems are offered to help understand the lecture material and assist with completing homeworks; they will also form the basis for some problems on the midterms. They are entirely optional, and feel free to skip if you understand a concept!
You should do these problems on paper or mentally first, and only THEN check the solution.
1. BareBones Haskell: Constructing Data, Defining Functions, Rewriting to Calculate Result Values
Consider the following data declaration:
data Numb = Z | S Numb | P Numb
We intend Z to represent 0, S to represent the successor of a Num, so (S Z) = 1, and P to represent the predecessor of a Num, so (P Z) = -1.
1.1. What data expression would represent 3?
1.2. What expression would represent -2?
1.3. Suppose we say the size of a data expression is the number of constructors it contains. List all the data expressions of size at most 2.
1.4. List all the data expressions of size 3.
Now consider the following data declaration, which will use our previous data declaration:
data Term = Val Numb | UMinus Term | Plus Term Term
1.5. List all data objects of type Term of size 3.
1.6. List all data objects of type Term of size 4.
1.7. What is the smallest data expression which uses the constructor Plus?
1.8. List all data expressions in Term of size 6 which use the constructor Plus.
Give the type of the following constructors or data expressions.
1.9. (S Z)
1.10. (Plus (Val Z) (Val Z))
1.11. Z
1.12. S
1.13. UMinus
1.14. Plus
Now consider adding the following functions to the data declarations given above:
red :: Numb -> Numb red Z = Z -- rule 0 red (P (S x)) = red x -- rule 1 red (S (P x)) = red x -- rule 2 red (P x) = (P (red x)) -- rule 3 red (S x) = (S (red x)) -- rule 4
1.15. For the following expression, list the subexpressions that are redexes for this set of rules, state which rule, and give the binding that would be created for x in the matching process:
(red (S (S (red (S (P (red Z))))))).
Make sure to pay attention to the order of the rules, and which rule would actually be considered first if two could possible match (as with rules 1 and 3).
1.16. Show how the expression (red (S (P (P Z)))) would be reduced through successive rewrite steps to an expression with no occurrences of the function name red, and
give the rule, underline the redex, and give the variable binding(s) that would be used in each step.
1.17. Do the same for: (red (S (S (P Z))))
1.18. Is is true that for any data expression D :: Numb that (red D) always terminates? What argument could you use to convince yourself of this?
1.19. Clearly, any negative number -N can be represented by an expression (P (P ... Z)) with N occurrences of P, and
any positive number M can be represented by an expression (S (S ... Z)) with M occurrences of S. Is it true that
for every data object D :: Num that (red D) terminates in such an expression representing a positive or negative number, or it is possible that the final
expression will still have a mix of S's and P's? If the former, give a reason why this is true,
if the latter, give an example showing this.
Now forget all the definitions from above, and start all over with these definitions:
data Numb = Z | S Numb deriving Show data Term = Val Numb | Plus Term Term deriving Show incr x = (S x) -- rule i0 add x Z = x -- rule a0 add x (S y) = (incr (add x y)) -- rule a1 eval (Val x) = x -- rule e0 eval (Plus x y) = add (eval x) (eval y) -- rule e1
1.20. Give the type of incr:
1.21. Give the type of add:
1.22. Give the type of eval
For the following, draw the tree corresponding to the expression.
1.23. (Plus (Val (S Z)) (Plus (Val Z) (Val (S (S Z)))))
1.24. (add x (S y))
1.25. (incr (add x y))
1.26. (add (eval (Plus (Val Z) (Val (S Z)))) (eval (Val Z)))
Recall that evaluation of expressions proceeds by searching for a redex (a subexpression where some rule defining a function will match) and rewriting the subexpression (using the bindings generated by the match). Consider the following algorithm, which thinks of the expression as a tree:
while the expression contains some function symbol:
for each subexpression in a PREORDER search of the expression:
for each rule in order (top to bottom) in the program:
if the rule matches:
then do one rewrite and start over at the top of
the while loop
If you need a review of recursive tree traversals, here is my CS 112 lecture on the subject: PDF
For each of the following, rewrite to a value (no function symbols, only constructors) using this algorithm and show the expressions at each step and underline the redex. With preorder, this means top-down left to right on trees, but on expressions written in text it essentially means scanning the expression from left to right, and rewriting the first redex you find; the beginning of this redex will be as far to the left as possible. Remember that after each rewrite step, you scan the expression all over again from the beginning.
1.27. (incr (S (incr (S Z))))
1.28. (add (S Z) (S Z))
1.29. (eval (Plus (Val (S Z)) (Val (S Z))))
Now repeat the previous, but using a POSTORDER traversal (bottom-up, left to right).
This process involves a postorder traversals on expressions considered as trees, but for an expression represented as text, it means performing the left-most rewrite step in which all variables are bound to expressions involving ONLY constructors (no function names). This is equivalent to what is ordinarily done in C and Java when parameters are passed.
1.30. (incr (S (incr (S Z))))
1.31. (add (S Z) (S Z))
1.32. (eval (Plus (Val (S Z)) (Val (S Z))))
Note carefully that preorder and postorder produce the exact same results in these cases.